Papers with tree-adjoining grammars
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages (2023.emnlp-main)
Copied to clipboard
| Challenge: | a class of tree-adjoining languages can be characterized by various two-level formalisms controlled by semiring-weighted CFGs and PDAs. |
| Approach: | They propose semiring-weighted versions of controllable CFGs and PDAs . they also introduce a WPDA normal form that is analogous to Chomsky's normal form for CFG . |
| Outcome: | The proposed algorithms are more time-efficient than the previous ones for LIG, PAA, and EPDA. |
Convergence and Diversity in the Control Hierarchy (2023.acl-long)
Copied to clipboard
| Challenge: | Weir has defined a hierarchy of language classes whose second member (L2) is generated by tree-adjoining grammars (TAG), linear indexed grammars, combinatory categorial grammars and head grammars. |
| Approach: | They propose to extend Weir's mechanism of control to give a definition of controllable pushdown automata (PDAs) they propose to use a stricter notion of equivalence to allow for finer-grained comparisons than weak equvalence. |
| Outcome: | The proposed language classes are d-weakly equivalent to Weir's original two-level grammar, but not d strongly equivalent. |